package com.cdream.basic.algorithm.leetcode.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author cdream
 * @date 6/22/21
 */
public class Offer38 {
    private int[] used;
    private List<String> res = new ArrayList<>();

    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        s = new String(chars);
        used = new int[26];
        for (char c : s.toCharArray()) {
            used[c - 'a']++;
        }
        dfs(s, 0, "");
        return res.toArray(new String[res.size()]);
    }

    private void dfs(String s, int index, String k) {
        if (k.length() == s.length()) {
            res.add(k);
        }
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && (s.charAt(i) == s.charAt(i - 1))) {
                continue;
            }
            int c = s.charAt(i) - 'a';
            if (used[c] == 0) {
                continue;
            }
            used[c]--;
            dfs(s, index + 1, k + s.charAt(i));
            used[c]++;
        }
    }
}
